//
// Created by wdq on 22-9-17.
//
#include <iostream>
#include <vector>
#include <cstring>
#include <set>

#define INFINITY 1000000
using namespace std;

struct Graph {
    vector<vector<int>> graph;
    int vexNum{};
    const char *names;

    explicit Graph(const char *names) : names(names) {
        vexNum = int(strlen(names));
        graph.resize(vexNum);
        for (auto &i: graph) {
            i.resize(vexNum);
        }
        for (auto &i: graph) {
            for (auto &j: i) {
                j = INFINITY;
            }
        }


    }

    void addArc(int head, int tail, int weight = 0) {
        graph[head][tail] = weight;
    }
};


void getShortestPathByDijkstra(Graph &G, int start) {
    vector<bool> choose(G.vexNum);
    vector<int> dist(G.vexNum);
    vector<int> pre(G.vexNum);
    for (int i = 0; i < G.vexNum; i++) {
        dist[i] = G.graph[start][i];
        pre[i] = dist[i] == INFINITY ? -1 : start;
    }
    choose[start] = true;
    for (int i = 0; i < G.vexNum; i++) {
        int minValue = INFINITY;
        int minIndex = -1;
        for (int j = 0; j < G.vexNum; j++) {
            if (!choose[j] && minValue > dist[j]) {
                minValue = dist[j];
                minIndex = j;
            }

        }
        if (minIndex == -1) {
            break;
        }
        choose[minIndex] = true;
        for (int j = 0; j < G.vexNum; j++) {
            if (!choose[j] && dist[j] > dist[minIndex] + G.graph[minIndex][j]) {
                dist[j] = dist[minIndex] + G.graph[minIndex][j];
                pre[j] = minIndex;
            }
        }
    }
    for (int i = 0; i < G.vexNum; i++) {
        vector<int> res;
        if (dist[i] == INFINITY) {
            cout << "no way !" << endl;
            continue;
        }
        res.emplace_back(i);
        for (int temp = pre[i]; temp != -1; temp = pre[temp]) {
            res.push_back(temp);
        }
        for (int j = int(res.size()) - 1; j >= 0; j--) {
            cout << res[j];
            if (j != 0) {
                cout << " -> ";
            }
        }
        printf("  minDist : %d", dist[i]);
        printf("\n");

    }

}

void getShortestPathByFloyd(Graph &G,int start) {
    vector<vector<int>> dist = G.graph;
    vector<vector<int>> pre(G.vexNum, vector<int>(G.vexNum));
    for (int i = 0; i < G.vexNum; i++) {
        for (int j = 0; j < G.vexNum; j++) {
            pre[i][j] = dist[i][j] == INFINITY ? -1 : i;
        }
    }

    for (int i = 0; i < G.vexNum; i++) {
        for (int j = 0; j < G.vexNum; j++) {
            for (int k = 0; k < G.vexNum; k++) {
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    pre[i][j] = pre[k][j];
                }
            }

        }
    }

    for (int i = 0; i < G.vexNum; i++) {
        vector<int> res;
        if (dist[start][i] == INFINITY) {
            cout << "no way !" << endl;
            continue;
        }
        res.emplace_back(i);
        for (int temp = pre[start][i]; temp != -1; temp = pre[start][temp]) {
            res.push_back(temp);
        }
        for (int j = int(res.size()) - 1; j >= 0; j--) {
            cout << res[j];
            if (j != 0) {
                cout << " -> ";
            }
        }
        printf("  minDist : %d", dist[start][i]);
        printf("\n");

    }



}

int main() {
    Graph g("012345");
    g.addArc(0, 2, 10);
    g.addArc(0, 4, 30);
    g.addArc(0, 5, 100);
    g.addArc(1, 2, 5);
    g.addArc(2, 3, 50);
    g.addArc(3, 5, 10);
    g.addArc(4, 3, 20);
    g.addArc(4, 6, 60);
//    getShortestPathByDijkstra(g, 0);
    getShortestPathByFloyd(g,0);
    return 0;
}